package pers.qianyu.month_202012.date_20201204;

import org.junit.*;

import java.util.*;

/**
 * 1642. 可以到达的最远建筑
 * https://leetcode-cn.com/problems/furthest-building-you-can-reach/
 *
 * @author mizzle rain
 * @date 2020-12-04 15:57
 */
public class FurthestBuilding {
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        PriorityQueue<Integer> q = new PriorityQueue<>();
        for (int i = 1; i < heights.length; i++) {
            int h = heights[i] - heights[i - 1];
            if (h > 0) {
                q.offer(h);
                if (ladders < q.size()) {
                    bricks -= q.poll();
                }
                if (bricks < 0) {
                    return i - 1;
                }
            }
        }
        return heights.length - 1;
    }

    @Test
    public void test1() {
        int[] arr = {4, 12, 2, 7, 3, 18, 20, 3, 19};
        int result = new FurthestBuilding().furthestBuilding(arr, 10, 2);
        System.out.println("result = " + result);
    }

    @Test
    public void test2() {
        int[] arr = {1, 5, 1, 2, 3, 4, 10000};
        int result = new FurthestBuilding().furthestBuilding(arr, 4, 1);
        Assert.assertEquals(result, 5);
    }
}
